
class Solution:
    def removeBoxes(self, boxes):
        boxes2 = []
        nowVal = None
        valNum = 0
        for i in range(len(boxes)):
            if boxes[i] != nowVal:
                if nowVal is not None:
                    boxes2.append((valNum, nowVal))
                valNum = 1
                nowVal = boxes[i]
            else:
                valNum += 1
        if nowVal is not None:
            boxes2.append((valNum, nowVal))

        def rb(stack, nowIndex, cache):
            key = (tuple(stack),nowIndex)
            if key in cache:
                return cache[key]
            grade = 0
            if nowIndex >= len(boxes2):
                if len(stack) == 0:
                    return 0
                val = stack.pop(-1)
                grade = val[0] * val[0] + rb(stack, nowIndex, cache)
            elif len(stack) == 0:
                stack.append(boxes2[nowIndex])
                grade = rb(stack, nowIndex + 1, cache)
            else:
                val = stack.pop(-1)
                if boxes2[nowIndex][1] == val[1]:
                    stack.append((val[0] + boxes2[nowIndex][0], val[1]))
                    grade = rb(stack, nowIndex + 1, cache)
                else:
                    copyStack = stack.copy()
                    grade = val[0] * val[0]+ rb(copyStack, nowIndex, cache)
                    stack.append(val)
                    stack.append(boxes2[nowIndex])
                    grade2 = rb(stack, nowIndex + 1, cache)
                    grade = max(grade, grade2)
            cache[key] = grade
            return grade

        return rb([], 0, {})


if __name__ == '__main__':
    so = Solution()
    boxes = [3,8,8,5,5,3,9,2,4,4,6,5,8,4,8,6,9,6,2,8,6,4,1,9,5,3,10,5,3,3,9,8,8,6,5,3,7,4,9,6,3,9,4,3,5,10,7,6,10,7]
    r = so.removeBoxes(boxes)
    print(r)
